// https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用虚拟头节点简化边界处理
// 2. 比较相邻节点值，发现重复立即删除所有重复节点
// 3. 内层循环跳过所有值相等的连续节点
// 4. 外层循环遍历整个链表，确保处理所有重复情况
// 5. 时间复杂度：O(N)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include "LinkedListUtils.h"

class Solution 
{
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if (head == nullptr) return head;

        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        auto cur = dummy;
        while (cur->next != nullptr && cur->next->next != nullptr)
        {
            if (cur->next->val == cur->next->next->val)
            {
                int val = cur->next->val;
                while (cur->next != nullptr && cur->next->val == val)
                {
                    cur->next = cur->next->next;
                }
            }
            else
            {
                cur = cur->next;
            }
        }

        auto result = dummy->next;
        delete dummy;

        return result;
    }
};

int main()
{
    vector<int> nodes1 = {1,2,3,3,4,4,5};
    vector<int> nodes2 = {1,1,1,2,3};

    Solution sol;

    auto l1 = createLinkedList(nodes1);
    auto l2 = createLinkedList(nodes2);

    auto r1 = sol.deleteDuplicates(l1);
    auto r2 = sol.deleteDuplicates(l2);

    printLinkedList(r1);
    printLinkedList(r2);

    return 0;
}